/**
 * 排序算法
 */
const arr = [5,8,6,3,9,2,1,7];
 /**
  * 冒泡排序1
  * 时间复杂度 O(n^2)
 */
function bubbleSort1(arr){
 for(let i=0;i<arr.length-1;i++){
   for(let j=0;j<arr.length-i-1;j++){
      let tmp = 0;
      if(arr[j]>arr[j+1]){
        tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
   }
 }
 return arr;
}
// console.log(bubbleSort1(arr))
 /**
  * 冒泡排序2
  * 优化：已经有序无须再继续排序，加标记来优化
  * 时间复杂度 O(n^2)
 */
function bubbleSort2(arr){
  for(let i=0;i<arr.length-1;i++){
    let isSorted = true; //有序标记，每一轮初始值为true
    for(let j=0;j<arr.length-i-1;j++){
       let tmp = 0;
       if(arr[j]>arr[j+1]){
         tmp = arr[j];
         arr[j] = arr[j+1];
         arr[j+1] = tmp;
         isSorted = false; //有元素交换，非有序置为false
       }
    }
    if(isSorted){
      break;
    }
  }
  return arr;
 }
// console.log(bubbleSort2(arr))
/**
  * 冒泡排序3
  * 优化:界定数列有序区，记录最后一次元素交换的位置
  * 时间复杂度 O(n^2)
 */
function bubbleSort3(arr){
  let lastExchangeIndex = 0;
  let sortBorder = arr.length - 1;
  for(let i=0;i<arr.length-1;i++){
    let isSorted = true; //有序标记，每一轮初始值为true
    for(let j=0;j<sortBorder;j++){
       let tmp = 0;
       if(arr[j]>arr[j+1]){
         tmp = arr[j];
         arr[j] = arr[j+1];
         arr[j+1] = tmp;
         isSorted = false; //有元素交换，非有序置为false
         lastExchangeIndex = j; //更新为最后一次交换元素的位置
       }
    }
    sortBorder = lastExchangeIndex;
    if(isSorted){
      break;
    }
  }
  return arr;
 }
// console.log(bubbleSort3(arr))

/**
  * 鸡尾酒排序
  * 基于冒泡排序的升级版：排序过程像钟摆一样，第一轮从左到右比较，第二轮从右向左比较........
  * 时间复杂度 O(n^2)
 */
function sort(arr){
  let tmp = 0;
  for(let i=0;i<arr.length/2;i++){
    let isSorted = true; //有序标记，每一轮初始值为true
    for(let j=i;j<arr.length - i - 1;j++){

       if(arr[j]>arr[j+1]){
         tmp = arr[j];
         arr[j] = arr[j+1];
         arr[j+1] = tmp;
         isSorted = false; //有元素交换，非有序置为false
       }
    }
    if(isSorted){
      break;
    }
    isSorted = true;
    for(let j=arr.length-i-1;j>i;j--){
      if(arr[j]<arr[j-1]){
        tmp = array[j];
              array[j] = array[j-1];
              array[j-1] = tmp;
              //因为有元素进行交换，所以不是有序的，标记变为false
              isSorted = false;
      }
    }
    if(isSorted){
      break;
    }
  }
  return arr;
 }
// console.log(sort(arr))

 /**
  * 快速排序1
  * 时间复杂度：最好情况每次划分所选择的中间数恰好将当前序列几乎等分，复杂度O(nlogn)
  * 最坏情况O(n^2)
  * 平均时间复杂度O(nlog2n)
  */
  function quickSort1(arr){
    if(arr.length <=1){
      return arr;
    }
    let index = Math.floor(arr.length/2)
    let qIndex = arr.splice(index,1);

    let big = [];
    let small= [];
    arr.map(num=>{
      if(num>qIndex){
         big.push(num);
      }else{
        small.push(num);
      }
    });
    return quickSort(small).concat(qIndex,quickSort(big))
  }
  // console.log(quickSort(arr))

   /**
  * 快速排序2:单边循环法
  * 时间复杂度：最好情况每次划分所选择的中间数恰好将当前序列几乎等分，复杂度O(nlogn)
  * 最坏情况O(n^2)
  * 平均时间复杂度O(nlog2n)
  */
 function quickSort2(arr,start,end){
  if(start>=end){
    return;
  }
  let pivotIndex = partion(arr,start,end);
  quickSort2(arr,start,pivotIndex-1);
  quickSort2(arr,pivotIndex+1,end);
}
function partion(arr,start,end){
   let pivot = arr[start];
   let mark = start;
   for(let i=start+1;i<=end;i++){
     if(arr[i]<pivot){
       mark++;
       let p = arr[mark];
       arr[mark] = arr[i];
       arr[i] = p;
     }
   } 
   arr[start] = arr[mark];
   arr[mark] = pivot;
   return mark;
}
// quickSort2(arr,0,arr.length-1)
// console.log(arr);


/**
 *快速选择算法: 数组中的第K个最大元素
  */

 /**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function partion(arr,lo,hi){
  let pivot = arr[lo];
  let mark = lo;
  for(let i=lo+1;i<=hi;i++){
      if(arr[i]<pivot){
          mark++;
          [arr[i],arr[mark]] = [arr[mark],[arr[i]]];
      }
  }
  arr[lo] = arr[mark];
  arr[mark] = pivot;
  return mark;
}
var findKthLargest = function(nums, k) {
 k = nums.length - k;
 let lo = 0,hi = nums.length -1 ;
 while(lo<=hi){
     let p = partion(nums,lo,hi);
     if(p == k){
         return nums[p]
     }else if (p<k){
         lo = p+1;
     }else {
         hi = p - 1;
     }
 }
 return -1;
};